﻿#pragma once
#include "Index.h"

class IFibonacciSequence
{
public:
	/**
	 * 斐波那契数列.
	 * https://www.nowcoder.com/practice/ee5d403c1172487f8c7915b3c3d924c6?tpId=230&tqId=2358261&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D230
	 * 
	 * 大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
	 * 斐波那契数列是一个满足
	 * fib(1)=1,fib(2)=1,
	 * fib(x)=fib(x-1)+fib(x-2)​ 当x>=3
	 * 数据范围：1≤n≤40
	 * 要求：空间复杂度O(1)，时间复杂度O(n) ，本题也有时间复杂度O(logn) 的解法
	 */
	virtual  int getFibonacc(int n) = 0;
};

class FibonacciSequence
{
public:
	class DP:public IFibonacciSequence
	{
	public:
		int getFibonacc(int n) override
		{
			if (n <= 0)
				return 0;
			if (n == 1)
				return 1;
			if (n == 2)
				return 1;
			int result;
			int a = 1, b = 1;
			for (int i = 3; i <= n; ++i)
			{
				result = a + b;
				a = b;
				b = result;
			}
			return result;
		}
	};
	class MathPow:public IFibonacciSequence
	{
	public:
		int getFibonacc(int n) override
		{
			const double sqrt5 = std::sqrt(5);
			const double a = (1 + sqrt5) / 2.0;
			const double b = (1 - sqrt5) / 2.0;
			const int result = std::round(1 / sqrt5 * (std::pow(a, n) - std::pow(b, n)));
			return result;
		}
	};
};



#ifdef DEV_TEST
#include <gtest/gtest.h>
class FibonacciTest:public SolutionTestor<IFibonacciSequence>
{
protected:
	void LoadSolutions(std::vector<IFibonacciSequence*>& solutions) override
	{
		solutions = {
			new FibonacciSequence::DP,
			new FibonacciSequence::MathPow,
		};
	}
};
TEST_F(FibonacciTest, getFibonacc)
{
	TestForSolutions([](IFibonacciSequence* solution)
		{
            int fib[] = { 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,
               17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,
               9227465,14930352,24157817,39088169,63245986,102334155 };

			const int fibSize = sizeof(fib) / sizeof(fib[0]);
			for(int i=1;i<=fibSize;++i)
				EXPECT_EQ(solution->getFibonacc(i), fib[i - 1]);
		});
}
#endif
